共计 7737 个字符，预计需要花费 20 分钟才能阅读完成。
数组结构
参考：http://8.129.6.198/post/173/
栈结构
栈 (stack) 又名堆栈，是一种运算受限的线性表，限定仅在表尾进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈，从一个栈删除元素称作出栈。
特点：后进先出，即 Last in First out (LIFO)。
class Stack {#items = [] //# 符号声明私有属性，ES13 新特性
pop() {return this.#items.pop() // 出栈
}
push(data) {return this.#items.push(data) // 进栈
}
peek() {return this.#items.at(-1) // 栈顶
}
isEmpty() {return this.#items.length === 0}
size() {return this.#items.length}
clear() {this.#items = []
}
toString() {return this.#items.join(" ")
}
}
// 十进制转 2 8 16 进制
function convert(decNumber, base) {let remStack = new Stack()
let number = decNumber
let string = ""
let baseString = "0123456789ABCDEF"
while (number > 0) {remStack.push(number % base)
number = Math.floor(number / base)
}
while (!remStack.isEmpty()) {string += baseString[remStack.pop()]
}
return string
}
convert(500, 16)队列结构
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾（入队），进行删除操作的端称为队头（出队）。队列中没有元素时，称为空队列。
特点：先进先出，即 First in First out(FIFO)。
封装与应用
class Queue {#items = {}
#lowCount = 0
#count = 0
dequeue() {if (this.isEmpty()) {return undefined}
let res = this.#items[this.#lowCount]
delete this.#items[this.#lowCount]
this.#lowCount++
return res // 出队
}
enqueue(data) {this.#items[this.#count] = data // 入队
this.#count++
}
front() {return this.#items[this.#lowCount] // 队头
}
isEmpty() {return this.size() === 0
}
size() {return this.#count - this.#lowCount}
clear() {this.#items = {}
this.#count = 0
this.#lowCount = 0
}
toString() {
let str = ""
for (let i = this.#lowCount; i < this.#count; i++) {str += `${this.#items[i]} `
}
return str
}
}
// 击鼓传花游戏
function game(list, num) {let queue = new Queue()
for (let i = 0; i < list.length; i++) {queue.enqueue(list[i])
}
while (queue.size() > 1) {for (let i = 0; i < num; i++) {queue.enqueue(queue.dequeue())
}
console.log(queue.dequeue(), " 淘汰了 ")
}
return queue.dequeue() + " 获胜 "}
game([" 张三 ", " 李四 ", " 王五 ", " 赵六 ", " 孙七 "], 7)双端队列
class DeQueue {#items = {}
#lowCount = 0 // 队头索引
#count = 0
removeFront() {if (this.isEmpty()) {return undefined}
let res = this.#items[this.#lowCount]
delete this.#items[this.#lowCount]
this.#lowCount++
return res
}
removeBack() {if (this.isEmpty()) {return}
this.#count--
const res = this.#items[this.#count]
delete this.#items[this.#count]
return res
}
addFront(data) {if (this.isEmpty()) {this.addBack(data)
} else {if (this.#lowCount > 0) {
this.#lowCount--
this.#items[this.#lowCount] = data
} else {
// #lowCount=0
for (let i = this.#count; i > 0; i--) {this.#items[i] = this.#items[i - 1]
}
}
}
}
addBack(data) {this.#items[this.#count] = data
this.#count++
}
peekFront() {return this.#items[this.#lowCount]
}
peekBack() {return this.#items[this.#count - 1]
}
isEmpty() {return this.size() === 0
}
size() {return this.#count - this.#lowCount}
clear() {this.#items = {}
this.#count = 0
this.#lowCount = 0
}
toString() {
let str = ""
for (let i = this.#lowCount; i < this.#count; i++) {str += `${this.#items[i]} `
}
return str
}
}
// 回文字符串检查
function test(str) {const lowstr = str.toLocaleLowerCase().split(" ").join("")
let dequeue = new DeQueue()
for (let i = 0; i < lowstr.length; i++) {dequeue.addBack(lowstr[i])
}
let isEqual = true
while (dequeue.size() > 1) {if (dequeue.removeFront() != dequeue.removeBack()) {
isEqual = false
break
}
}
return isEqual
}
test(" 上海自来水来自海上 ")链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点 (链表中每一个元素称为结点) 组成，结点可以在运行时动态生成。每个结点包括两个部分: 一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的特点
- 插入、删除数据效率高 O(1)级别 (只需更改指针指向即可)，随机访问效率低 O(n) 级别(需要从链头至链尾进行遍历)
- 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。
单链表
每个节点只包含一个指针，即后继指针。
class Node {constructor(element) {
this.element = element
this.next = null
}
}
class LinkedList {constructor() {
this.count = 0
this.head = null
}
push(element) {const node = new Node(element)
if (this.head === null) {this.head = node} else {
let current = this.head
while (current.next !== null) {current = current.next}
current.next = node
}
this.count++
}
getNodeAt(index) {if (index >= 0 && index < this.count) {
let node = this.head
for (let i = 0; i < index; i++) {node = node.next}
return node
}
return
}
// 指定位置删除
removeAt(index) {if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {this.head = this.head.next} else {let previous = this.getNodeAt(index - 1)
current = previous.next
previous.next = current.next
}
this.count--
return current.element
}
return
}
equalFn(a, b) {return JSON.stringify(a) === JSON.stringify(b)
}
indexOf(element) {
let current = this.head
for (let i = 0; i < index; i++) {if (this.equalFn(element, current.element)) {return i}
current = current.next
}
return -1
}
// 指定元素删除
remove(element) {const index = this.indexOf(element)
return this.removeAt(index)
}
insert(element, index) {if (index >= 0 && index <= this.count) {const node = new Node(element)
if (index === 0) {
const current = this.head
node.next = current
this.head = node
} else {const previous = this.getNodeAt(index - 1)
const current = previous.next
node.next = current
previous.next = node
}
this.count++
return true
}
return false
}
isEmpty() {return this.size() === 0
}
size() {return this.count}
getHead() {return this.head}
}
// 回文字符串检查
function test(str) {const lowstr = str.toLocaleLowerCase().split(" ").join("")
let sll = new LinkedList()
for (let i = 0; i < lowstr.length; i++) {sll.push(lowstr[i])
}
let isEqual = true
while (sll.size() > 1) {if (sll.removeAt(0) !== sll.removeAt(sll.size() - 1)) {
isEqual = false
break
}
}
return isEqual
}
test(" 上海自来水来自海上 ")击鼓传花游戏使用单链表：
// 击鼓传花游戏
function game(list, num) {let queue = new LinkedList()
for (let i = 0; i < list.length; i++) {queue.push(list[i])
}
while (queue.size() > 1) {for (let i = 0; i < num; i++) {queue.push(queue.removeAt(0))
}
console.log(queue.removeAt(0), " 淘汰了 ")
}
return queue.removeAt(0) + " 获胜 "
}
game([" 张三 ", " 李四 ", " 王五 ", " 赵六 ", " 孙七 "], 7)十进制转 2 8 16 进制：
// 十进制转 2 8 16 进制
function convert(decNumber, base) {let remStack = new LinkedList()
let number = decNumber
let string = ""
let baseString = "0123456789ABCDEF"
while (number > 0) {remStack.push(number % base)
number = Math.floor(number / base)
}
while (!remStack.isEmpty()) {string += baseString[remStack.removeAt(remStack.size() - 1)]
}
return string
}
convert(500, 16)双链表
class DoublyNode extends Node {constructor(element) {super(element)
this.prev = null
}
}
class DoublyLinkedList extends LinkedList {constructor() {super()
this.tail = null
}
push(element) {const node = new DoublyNode(element)
if (this.head === null) {
this.head = node
this.tail = node
} else {
this.tail.next = node
node.prev = this.tail
this.tail = node
}
this.count++
}
remove(element) {const index = this.indexOf(element)
return this.removeAt(index)
}
insert(element, index) {if (index >= 0 && index <= this.count) {const node = new DoublyNode(element)
let current = this.head
if (index === 0) {if (this.head === null) {
this.head = node
this.tail = node
} else {
node.next = this.head
this.head.prev = node
this.head = node
}
} else if (index === this.count) {
current = this.tail
current.next = node
node.prev = current
this.tail = node
} else {const previous = this.getNodeAt(index - 1)
current = previous.next
node.next = current
current.prev = node
previous.next = node
node.prev = previous
}
this.count++
return true
}
return false
}
removeAt(index) {if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {
this.head = current.next
if (this.count === 1) {this.tail = null} else {this.head.prev = null}
} else if (index === this.count - 1) {
current = this.tail
this.tail = current.prev
this.tail.next = null
} else {let previous = this.getNodeAt(index - 1)
current = previous.next
previous.next = current.next
current.next.prev = previous
}
this.count--
return current.element
}
return
}
getHead() {return this.head}
getTail() {return this.tail}
}循环链表
循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针 (tail.next) 不是 undefined，而是指向第一个元素(head)。
class CircularLinkedList extends LinkedList {constructor() {super()
}
push(element) {const node = new Node(element)
let current
if (this.head === null) {this.head = node} else {current = this.getNodeAt(this.size() - 1)
current.next = node
}
node.next = this.head
this.count++
}
insert() {if (index >= 0 && index <= this.count) {const node = new Node(element)
let current = this.head
if (index === 0) {if (this.head === null) {
this.head = node
node.next = this.head
} else {
node.next = current
this.head = node
current = this.getNodeAt(this.size() - 1)
current.next = this.head
}
} else {const previous = this.getNodeAt(index - 1)
node.next = previous.next
previous.next = node
}
this.count++
return true
}
return false
}
removeAt(index) {if (index >= 0 && index < this.count) {
let current = this.head
if (index === 0) {if (this.size() === 1) {this.head = null} else {let last = this.getNodeAt(this.size() - 1)
this.head = this.head.next
last.next = this.head
}
} else {const previous = this.getNodeAt(index - 1)
current = previous.next
previous.next = current.next
}
this.count--
return current.element
}
return
}
}
正文完
